package com.leetcode.根据算法进行分类.排序算法相关.桶排序;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author: ZhouBert
 * @date: 2021/3/29
 * @description: 220. 存在重复元素 III
 * https://leetcode-cn.com/problems/contains-duplicate-iii/
 */
public class B_220_存在重复元素III {

    static B_220_存在重复元素III action = new B_220_存在重复元素III();

    public static void main(String[] args) {
        test1();
        test2();
        test3();
        test4();
        test5();
        test6();
        test7();
    }


    static void test1() {
        //false
        int[] nums = new int[]{1, 5, 9, 1, 5, 9};
        int k = 2, t = 3;
        boolean res = action.containsNearbyAlmostDuplicateByBucket(nums, k, t);
        System.out.println("res = " + res);
    }

    static void test2() {
        //true
        int[] nums = new int[]{1, 2, 2, 3, 4, 5};
        int k = 3, t = 0;
        boolean res = action.containsNearbyAlmostDuplicateByBucket(nums, k, t);
        System.out.println("res = " + res);
    }

    static void test3() {
        //true
        int[] nums = new int[]{1, 0, 1, 1};
        int k = 1, t = 2;
        boolean res = action.containsNearbyAlmostDuplicateByBucket(nums, k, t);
        System.out.println("res = " + res);
    }

    static void test4() {
        //true
        int[] nums = new int[]{-3, 3, -6};
        int k = 2, t = 3;
        boolean res = action.containsNearbyAlmostDuplicateByBucket(nums, k, t);
        System.out.println("res = " + res);
    }

    static void test5() {
        //true
        int[] nums = new int[]{8, 7, 15, 1, 6, 1, 9, 15};
        int k = 1, t = 3;
        boolean res = action.containsNearbyAlmostDuplicateByBucket(nums, k, t);
        System.out.println("res = " + res);
    }

    static void test6() {
        //true
        int[] nums = new int[]{1, 14, 23, 45, 56, 2, 3};
        int k = 1, t = 10;
        boolean res = action.containsNearbyAlmostDuplicateByBucket(nums, k, t);
        System.out.println("res = " + res);
    }

    static void test7() {
        //true
        int[] nums = new int[]{-2147483648, 2147483647};
        int k = 1, t = 1;
        boolean res = action.containsNearbyAlmostDuplicateByBucket(nums, k, t);
        System.out.println("res = " + res);

    }

    static void test8() {

    }

    /**
     * i 和 j 的差的绝对值也小于等于 ķ 。
     * --
     * 失策了，使用单纯的滑动窗口会漏掉一些情况，所以我决定用暴力的方法进行遍历。
     *
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public boolean containsNearbyAlmostDuplicateBySlideWindowFail(int[] nums, int k, int t) {
        int len = nums.length;
        if (len < 2) {
            return false;
        }

        int begin = 0, end = 1;

        //初始化滑动窗口
        while (end <= k) {
            if (Math.abs(nums[end++] - nums[begin]) <= t) {
                return true;
            }
        }
        //此时 end = begin+t+1
        int endIndex = len - 1;
        begin++;
        while (begin < endIndex) {
            if (Math.abs(nums[end] - nums[begin]) <= t) {
                return true;
            } else {
                while (++begin < end) {
                    if (Math.abs(nums[end] - nums[begin]) <= t) {
                        return true;
                    }
                }
            }

            //此时 begin == end
            int tempEnd = begin + k;
            tempEnd = Math.min(tempEnd, len);
            end++;
            while (end < tempEnd) {
                if (Math.abs(nums[end++] - nums[begin]) <= t) {
                    return true;
                }
            }
            if (end == len) {
                break;
            }
        }
        return false;
    }

    /**
     * 考虑int 越界问题！
     * 不是滑动窗口不能解决问题，而是滑动窗口TLE 了！
     *
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public boolean containsNearbyAlmostDuplicateBySlideWindow(int[] nums, int k, int t) {
        int len = nums.length;
        if (len < 2) {
            return false;
        }

        int begin = 0, end = 1;
        while (begin < len) {
            int e = begin + k >= len ? len - 1 : begin + k;
            while (end <= e) {
                if (Math.abs((long) nums[end] - nums[begin]) <= t) {
                    return true;
                } else {
                    end++;
                }
            }
            begin++;
            end = begin + 1;
        }

        return false;
    }


    /**
     * 当间隔为1，2,3,...k
     * TLE
     *
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public boolean containsNearbyAlmostDuplicateByForce(int[] nums, int k, int t) {
        int len = nums.length;
        if (len < 2) {
            return false;
        }
        for (int interval = 1; interval <= k; interval++) {
            int endIndex = len - interval;
            for (int i = 0; i < endIndex; i++) {
                //不能使用 Math.abs 不然无法处理越界的问题，只能先转为 long 了
                long n1 = nums[i + interval];
                long n2 = nums[i];
//				if (Math.abs(nums[i+interval] - nums[i]) <= t) {
//					return true;
//				}
                long diff = n1 - n2;
                if ((diff >= 0 && diff <= t) || (diff < 0 && (-diff) <= t)) {
                    return true;
                }
            }
        }
        return false;
    }


    /**
     * 使用桶排序
     * 索引之间的相差 小于等于 k
     * 值之间的相差 小于等于 t
     * --
     * 分析：
     * eg.对于数组：[1, 5, 9, 1, 5, 9],得到:
     * min=1,max=9
     * 分为三个桶：[1,4),[4,7),[7,10)
     * 遍历一遍，对于落入桶中的元素，进行索引的判断。
     * 感觉像是另外一种记忆话搜索！！！牛逼
     * --
     * 但是用数组桶不好解决 int 越界的问题。以及容器创建太多没有必要的桶。
     * 最好是按需添加~！！！
     *
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        int len = nums.length;
        if (len < 2) {
            return false;
        }
        long max = nums[0], min = max;
        for (int i = 0; i < len; i++) {
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        if (t == 0) {
            //当t == 0 时，每个数放一个桶
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < len; i++) {
                if (map.containsKey(nums[i])) {
                    Integer lastIndex = map.get(nums[i]);
                    if (i - lastIndex <= k) {
                        return true;
                    } else {
                        map.put(nums[i], i);
                    }
                } else {
                    map.put(nums[i], i);
                }

            }
            return false;
        }
        int size = (int) (max - min) / t + 1;
//		if ((int) (max - min) != 0){
//			size++;
//		}
        //记录 maxIndex
        // size 只能为 int ,这样就很难处理 int 越界的问题了！
        int[] buckets = new int[size];
        Arrays.fill(buckets, -1);
        int index = 0;
        int diff = t + 1;
        for (int i = 0; i < len; i++) {
            index = (int) ((nums[i] - min) / diff);
            if (buckets[index] != -1) {
                //说明已经有了
                if (i - buckets[index] <= k) {
                    return true;
                } else {
                    buckets[index] = i;
                }
            } else {
                buckets[index] = i;
            }
        }
        return false;
    }

    /**
     * 既然滑窗不能用，只能考虑桶排序了！
     *
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public boolean containsNearbyAlmostDuplicateByBucket(int[] nums, int k, int t) {
        int n = nums.length;
        Map<Long, Long> map = new HashMap<Long, Long>();
        long w = (long) t + 1;
        for (int i = 0; i < n; i++) {
            long id = getID(nums[i], w);
            if (map.containsKey(id)) {
                return true;
            }
            if (map.containsKey(id - 1) && Math.abs(nums[i] - map.get(id - 1)) < w) {
                return true;
            }
            if (map.containsKey(id + 1) && Math.abs(nums[i] - map.get(id + 1)) < w) {
                return true;
            }
            map.put(id, (long) nums[i]);
            if (i >= k) {
                map.remove(getID(nums[i - k], w));
            }
        }
        return false;
    }

    public long getID(long x, long w) {
        if (x >= 0) {
            return x / w;
        }
        return (x + 1) / w - 1;
    }
}
